#include <iostream>
#include <vector>
using namespace std;

namespace segment_tree
{

int size;
vector<long> arr;
vector<long long> isum;
vector<long> imax;

void up(int i)
{
	isum[i] = isum[i << 1] + isum[i << 1 | 1];
	imax[i] = max(imax[i << 1], imax[i << 1 | 1]);
}

void build(int l, int r, int i)
{
	if (l == r) {
		isum[i] = arr[l];
		imax[i] = arr[l];
	} else {
		int mid = (l + r) >> 1;
		build(l, mid, i << 1);
		build(mid + 1, r, i << 1 | 1);
		up(i);
	}
}

void reset(int k, long v, int l = 1, int r = size, int i = 1)
{
	if (l == r) {
		arr[l] = v;
		isum[i] = arr[l];
		imax[i] = arr[l];
	} else {
		int mid = (l + r) >> 1;
		if (k <= mid) {
			reset(k, v, l, mid, i << 1);
		} else {
			reset(k, v, mid + 1, r, i << 1 | 1);
		}
		up(i);
	}
}

void mod(int jobl, int jobr, long x, int l = 1, int r = size, int i = 1)
{
	if (x > imax[i]) {
		return;
	}

	if (l == r) {
		arr[l] = arr[l] % x;
		isum[i] = arr[l];
		imax[i] = arr[l];
	} else {
		int mid = (l + r) >> 1;
		if (jobl <= mid) {
			mod(jobl, jobr, x, l, mid, i << 1);
		}
		if (mid < jobr) {
			mod(jobl, jobr, x, mid + 1, r, i << 1 | 1);
		}

		up(i);
	}
}

long long query(int jobl, int jobr, int l = 1, int r = size, int i = 1)
{
	if (jobl <= l && r <= jobr) {
		return isum[i];
	}

	int mid = (l + r) >> 1;
	long long ans = 0;
	if (jobl <= mid) {
		ans += query(jobl, jobr, l, mid, i << 1);
	}
	if (mid < jobr) {
		ans += query(jobl, jobr, mid + 1, r, i << 1 | 1);
	}

	return ans;
}

}; // namespace segment_tree

using namespace segment_tree;

int main()
{
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);

	int n = 0, m = 0;
	cin >> n >> m;
	segment_tree::size = n;
	arr.resize(n + 1, 0);
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}

	isum.resize(n << 2, 0);
	imax.resize(n << 2, 0);
	build(1, n, 1);

	long x;
	for (int i = 0, op, l, r, k; i < m; i++) {
		cin >> op;
		if (op == 1) {
			cin >> l >> r;
			cout << query(l, r) << '\n';
		} else if (op == 2) {
			cin >> l >> r >> x;
			mod(l, r, x);
		} else if (op == 3) {
			cin >> k >> x;
			reset(k, x);
		}
	}

	return 0;
}
/*
5 5
1 2 3 4 5
1 1 5
3 2 5
1 1 5
1 1 2
*/